package william.string;

/**
 * @author ZhangShenao
 * @date 2024/4/24
 * @description <a href="https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/description/?envType=study-plan-v2&envId=top-interview-150">...</a>
 */
public class Leetcode28_找到字符串中第一个匹配项的下标 {
    /**
     * 采用Boyer-Moore算法,即暴力求解算法
     * 设定haystack的长度为M,needle的长度为N
     * 则从头开始,找到haystack中的每一个长度为N的字符串,判断与needle是否匹配
     * 如果找到了一个匹配的字符串,则直接返回当前的起始下标,否则返回-1
     * <p>
     * 时间复杂度O(M*N) 即haystack的长度 * needle的长度
     * 空间复杂度O(1)
     */
    public int strStr(String haystack, String needle) {
        //边界条件校验
        if (haystack == null || haystack.isEmpty() || needle == null) {
            return -1;
        }
        if (needle.isEmpty()) {
            return 0;
        }

        int M = haystack.length();
        int N = needle.length();
        if (M < N) {
            return -1;
        }

        //从头开始,找到haystack中的每一个长度为N的字符串,判断与needle是否匹配
        for (int i = 0; i + N <= M; i++) {
            boolean matched = true;
            for (int j = 0; j < N; j++) {
                if (haystack.charAt(i + j) != needle.charAt(j)) {
                    matched = false;
                    break;
                }
            }

            //找到匹配项,返回起始下标
            if (matched) {
                return i;
            }
        }

        //未找到匹配项,返回-1
        return -1;
    }
}
